#  三个排序
# 2024年5月31日10:48:53
def selection_sort(list1):
    # 升序排序
    # 外层确定位置，把最小放第一个，类推到倒数第二个位置，完成排序
    # 内层每个位置，都和剩余的比
    for i in range(len(list1) - 1):
        for j in range(i + 1, len(list1)):
            if list1[i] > list1[j]:
                list1[i], list1[j] = list1[j], list1[i]


# bubble_sort 2024年5月31日10:53:53
def bubble_sort(list1):
    # 外层循环判断交换次数，将大数沉底，小数冒泡上来，将n-1个数沉底，那么排序就完成了
    # 内层相邻交换
    for i in range(len(list1)-1):
        for j in range(len(list1)-1-i):  # 因为有j+1，遍历下标需要时len-1，否则越界
            if list1[j] > list1[j+1]:
                list1[j], list1[j+1] = list1[j+1], list1[j]

# 伪快排
def v_quick_sort(list1):
    if len(list1) <=1:
        return list1
    pivote = list1[0]
    greater = [i for i in list1[1:] if i > pivote]
    less = [i for i in list1[1:] if i <= pivote]
    return v_quick_sort(less) + [pivote] + v_quick_sort(greater)


def quick_sort(L):
    return q_sort(L, 0, len(L)-1)


def q_sort(L, left, right):
    if left < right:
        pivot = partition(L, left, right)
        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L


def partition(L, left, right):
    pivot = L[left]
    while left < right:
        while left < right and L[right] >= pivot:
            right -= 1
        L[left] = L[right]
        while left < right and L[left] <= pivot:
            left += 1
        L[right] = L[left]
    L[left] = pivot
    return left


import random
temp = [random.randint(0, 100000) for i in range(100000)]
temp1 = temp[:]
temp2 = temp[:]
temp3 = temp[:]
temp4 = temp[:]




# 开始排序
import time
# start = time.clock()
# selection_sort(temp)
# print("select", time.clock() - start)
# print(temp)
#
# start = time.clock()
# bubble_sort(temp1)
# print("bubble", time.clock() - start)
# print(temp1)

start = time.clock()
quick_sort(temp2)
print("quick", time.clock() - start)

start = time.clock()
temp3 = v_quick_sort(temp3)
print("v_quick", time.clock() - start)

start = time.clock()
temp4.sort()
print("list_sort", time.clock() - start)

# print(temp4)
# print(temp3)
# print(temp2)